package linkedlist;

/**
 * @author hgvgh
 * @see https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * @version 1.0
 * @description 两个链表合并
 * @date 2022/1/2
 */
public class MergeTwoLinkedList {

  public static void main(String[] args) {
    ListNode l1 = new ListNode(1);
    ListNode listNode2 = new ListNode(2);
    l1.next = listNode2;
    ListNode listNode3 = new ListNode(3);
    listNode2.next = listNode3;

    ListNode l2 = new ListNode(4);
    ListNode listNode22 = new ListNode(5);
    l2.next = listNode22;
    ListNode listNode23 = new ListNode(6);
    listNode22.next = listNode23;

    ListNode listNode = mergeTwoLists(l1, l2);

    while (listNode != null) {
      System.out.println(listNode.val);
      listNode = listNode.next;
    }

  }

  public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 使用带头结点的链表解决问题
    // 待输出链表的头部
    ListNode head = new ListNode();

    // 待输出链表的 last 结点
    ListNode last = head;
    while(l1 != null && l2 != null) {
      if(l1.val > l2.val) {
        last.next = l2;
        l2 = l2.next;
      }else{
        last.next = l1;
        l1 = l1.next;
      }
      last = last.next;
    }

    // l1 或 l2 可能还有剩余结点没有合并，
    // 由于从上面的 while 循环中退出， 那么链表 l1 和 l2 至少有一个已经遍历结束
    if(l1 != null) last.next = l1;
    if(l2 != null) last.next = l2;

    return head.next;

  }


  public static class ListNode {

    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
      this.val = val;
    }

    ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }

}
